// IDA*
#include <iostream>
#include <stdio.h>
#include <string.h>

#define MAXN 10

using namespace std;

int map[MAXN][MAXN], xx[4] = {1, -1, 0, 0}, yy[4] = {0, 0, 1, -1}, status[MAXN][MAXN]; // status[i][j]=1表示(i,j)已被染色,在联通块内,2表示(i,j)没被染色,与联通块相邻,3表示(i,j)未被染色，与联通块不相邻
int N, depth;

bool check(int x, int y) // 检查(x,y)是否越界,是返回false
{
    if (x > N || x < 1 || y > N || y < 1)
        return false;
    return true;
}

void flood(int x, int y, int col) // 以(x,y),颜色为col的格子为起点flood
{
    status[x][y] = 1; // 将当前格子加入联通块
    for (int dir = 0; dir < 4; dir++)
    {
        int tx = x + xx[dir]; // 移动格子到相邻的(tx,ty)
        int ty = y + yy[dir];
        if (!check(tx, ty))
            continue; // 越界则跳过
        if (status[tx][ty] == 1)
            continue;           // 在联通块内，跳过
        if (map[tx][ty] == col) // 是可以染的颜色
            flood(tx, ty, col);
        else
            status[tx][ty] = 2; // 符合条件但是不能染色，则表明(tx,ty)是与联通块相邻的格子
    }
}

int get_cnt(int col) // 如果对剩余的col色方块染色，最多能染多少个方块
{
    int cnt = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
        {
            if (status[i][j] == 2 && map[i][j] == col) // 如果当前格子颜色与col相同且与联通块相邻，对它和相邻的方块染色,由于染色后会更新status数组，所以不会存在重复问题
            {
                cnt++; // 增加
                flood(i, j, col);
            }
        }
    return cnt;
}

int h() // 估价函数,表示除了联通块的部分，还有多少种颜色，颜色数代表对当前状态未来步数的估计
{
    int tot = 0;
    bool flag[6];
    memset(flag, false, sizeof(flag));
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
        {
            if (status[i][j] != 1 && !flag[map[i][j]]) // 当前点不在联通块内，且该颜色是新种类颜色
            {
                tot++;
                flag[map[i][j]] = true;
            }
        }
    return tot;
}

bool IDAstar(int dep) // 在深度为dep的状态下搜索,搜索成功返回true,不成功返回false
{
    if (dep == depth)
        return h() == 0; // 搜索深度到达目标深度，返回状态是否与目标状态相同
    if (dep + h() > depth)
        return false;           // 预计深度超了，直接返回false
    for (int i = 0; i < 6; i++) // 染第i种颜色
    {
        int now[MAXN][MAXN]; // now数组用于备份status
        memcpy(now, status, sizeof(status));
        if (get_cnt(i) == 0) // 染不了任何一个方块，即无法染色
            continue;
        if (IDAstar(dep + 1))
            return true;                  // 加深搜索可行，返回true
        memcpy(status, now, sizeof(now)); // 将status数组复原
    }
    return false; // 六种颜色都不行，则搜索失败
}

int main()
{
    while (1)
    {
        memset(map, 0, sizeof(map));
        memset(status, 0, sizeof(status));
        scanf("%d", &N);
        if (N == 0)
            return 0;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                scanf("%d", &map[i][j]);
        flood(1, 1, map[1][1]); // 先操作一次
        depth = h();
        while (1)
        {
            if (IDAstar(0))
                break; // 搜索成功则跳出
            depth++;   // 不成功则增大深度阈值，重新搜索(迭代加深)
        }
        printf("%d\n", depth); // 输出深度
    }
    return 0;
}